Tháng 8 năm 1988, sau khi tốt nghiệp trường Sĩ quan Pháo, trường Antonio Maceo, Nguyễn Hải Anh nhận quân hàm Thiếu úy, là Sĩ quan đối ngoại Đoàn Chuyên gia Quân sự 385 của Quân đội nhân dân Việt Nam tại Cuba. Tháng 1 năm 1993, ông là Thượng úy, Sĩ quan phiên dịch tiếng Tây Ban Nha của Đoàn 871, Bộ Quốc phòng. Công tác cho đến năm 1995, ông trở về nước và xuất ngũ, được điều tới Ủy ban Thanh niên Việt Nam làm Chuyên viên đối ngoại, đến tháng 8 cùng năm thì tới Bảo hiểm Xã hội Việt Nam, là Chuyên viên phụ trách công tác đối ngoại khi cơ quan bảo hiểm xã hội này vừa được thành lập.[3] Sang tháng 9 năm 1996, ông quay trở lại hoạt động thanh niên, là Chuyên viên Ban Quốc tế, Trung ương Đoàn Thanh niên Cộng sản Hồ Chí Minh, thăng chức Phó Trưởng ban Quốc tế từ tháng 12 năm 1998, đồng thời là Ủy viên Ban Chấp hành Trung ương Đoàn khóa VII, khóa VIII, Ủy viên Ban Chấp hành của các tổ chức xã hội như Hội Doanh nghiệp Trẻ Việt Nam, Hội Hữu nghị Việt Nam – Cuba, Hội Hữu nghị Việt Nam – Canada.[3]

Tháng 9 năm 2004, Nguyễn Hải Anh được điều tới Tổng cục Du lịch, nhậm chức Phó Bí thư Chi bộ, Phó Vụ trưởng Vụ Hợp tác quốc tế. Đến tháng 1 năm 2008, ông chuyển vị trí làm Phó Cục trưởng Cục Hợp tác quốc tế của Bộ Văn hóa, Thể thao và Du lịch, tiếp tục chuyển làm Phó Bí thư Chi bộ, Vụ trưởng Vụ Thi đua – Khen thưởng của Bộ Văn hóa từ tháng 1 năm 2011, đồng thời là Ủy viên Ban Thường vụ Trung ương Hội Hữu nghị Việt Nam – Cuba, Trung ương Hội Hữu nghị Việt Nam – Tây Ban Nha.[3] Vào tháng 4 năm 2014, ông được điều về tỉnh Tuyên Quang, chỉ định vào Ban Chấp hành Đảng bộ tỉnh, là Ủy viên Ban cán sự Đảng, Phó Chủ tịch Ủy ban nhân dân tỉnh Tuyên Quang.[4] Ở Tuyên Quang, ông tiếp tục là Tỉnh ủy viên khóa 2015–2020,[5] giữ các vị trí khác như Ủy viên Hội đồng nhân dân tỉnh, Chủ tịch Hội đồng Trường Đại học Tân Trào.[6]

Sang tháng 3 năm 2019, Nguyễn Hải Anh được điều tới Hội Chữ thập đỏ Việt Nam, là Ủy viên Đảng đoàn, Phó Chủ tịch, Tổng thư ký Hội Chữ thập đỏ Việt Nam,[7] kiêm nhiệm Bí thư Đảng ủy cơ quan Trung ương Hội, Ủy viên Đoàn Chủ tịch Liên hiệp các tổ chức hữu nghị Việt Nam, Phó Chủ tịch Hội Hữu nghị Việt Nam – Tây Ban Nha. Năm 2021, với sự giới thiệu của Hội Chữ thập đỏ, ông tham gia ứng cử đại biểu Quốc hội từ Đồng Tháp,[8] tại đơn vị bầu cử số 2 gồm thành phố Cao Lãnh, huyện Thanh Bình, Cao Lãnh, Tháp Mười,[9] rồi trúng cử Đại biểu Quốc hội khóa XV với tỷ lệ 60,59%.[10] Trong nhiệm kỳ này, ông còn là là Ủy viên Ủy ban Đối ngoại của Quốc hội.[11]